/**
 * 给定N个点，每次移动只能将一个点沿上下左右方向移动一步
 * 问K步以内能够得到的最小正方形包围盒的边长是多少
 * 很明显二分，对每一个limit，问能否在K步以内将点移进边长为limit的正方形
 * 可以发现X、Y坐标可以单独考虑，问题转化为：
 * 在数轴上有N个点，每次或左或右移动1，将其移动到limit段内，最少要几步
 * 基于贪心，显然段的起点或者终点必然存在已知点。可以分别考虑。
 * 对每个点i，假设right点是右边第一个距离i超出limit的点，
 * 则若想将所有点移动到[Xi, Xi+limit]范围内，所需的步数是：
 * SIGMA{Xi - Xj, j是i左边的点} + SIGMA{Xj - (Xi + limit), j>=right}
 * 利用前缀和很容易求出上式的结果
 * 同理可以对每个点i，求出将所有点移进[Xi-limit, Xi]范围内的步数
 * 上述所有最小值就是X方向的答案，再加上Y方向的答案就将所有点移进limit包围盒的答案
 * 看齐是否超过K，进行二分操作即可
 * O(NlogN + MaxChalogN)
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

using llt = long long;
using vi = vector<int>;

llt K;
int N;

vector<llt> X, Y;
vector<llt> SX, SY, RX, RY;

llt procQian(llt limit, const vector<llt> & vec, const vector<llt> & s){
    llt ans = -1;
    int left = 0, right = 0;
    while(1){
        while(right < N and vec[right] - vec[left] <= limit) ++right;
        if(right == N) {
            
            break;
        }

        llt tmp = (s[N - 1] - s[right - 1]) - (N - right + 0LL) * (vec[left] + limit + 0LL);
        if(left) tmp += (left + 0LL) * vec[left] - s[left - 1];

        if(-1 == ans or tmp < ans) ans = tmp;
        ++left;
    }
    if(-1 == ans) return 0;
    return ans;
}

llt procHou(llt limit, const vector<llt> & vec, const vector<llt> & s){
    llt ans = -1;
    int left = N - 1, right = N - 1;
    while(1){
        while(left >= 0 and vec[right] - vec[left] <= limit) --left;
        if(-1 == left) break;

        llt tmp = (s[N - 1] - s[right]) - (N - right - 1LL) * vec[right];
        tmp += (left + 1LL) * (vec[right] - limit + 0LL) - s[left];
        if(-1 == ans or tmp < ans) ans = tmp;

        --right; 
    }
    if(-1 == ans) return 0;
    return ans;
}

bool check(llt limit){
    auto a = min(procQian(limit, X, SX), procHou(limit, X, SX));
    auto b = min(procQian(limit, Y, SY), procHou(limit, Y, SY));
    return a + b <= K;
}

int proc(){
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    
    SX.assign(N, 0); SY.assign(N, 0);
    RX.assign(N, 0); RY.assign(N, 0);
    
    SX[0] = X[0]; SY[0] = Y[0];
    for(int i=1;i<N;++i) SX[i] = X[i] + SX[i - 1], SY[i] = Y[i] + SY[i - 1];

    RX[N - 1] = X[N - 1]; RY[N - 1] = Y[N - 1];
    for(int i=N-2;i>=0;--i)RX[i] = RX[i + 1] + X[i], RY[i] = Y[i] + RY[i + 1];

    llt left = 0, right = max(X[N-1] - X[0], Y[N-1] - Y[0]), mid;
    do{
        mid = (left + right) >> 1;
        if(check(mid)) right = mid - 1;
        else left = mid + 1;
    }while(left <= right);
    return left;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    cin >> N >> K;
    X.assign(N, 0); Y.assign(N, 0);
    for(int i=0;i<N;++i) cin >> X[i] >> Y[i];
    cout << proc() << endl;
    return 0;
}